package q138;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 138. 随机链表的复制
 */
public class Solution {

    Map<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node newHead = new Node(head.val);
        map.put(head, newHead);
        if (head.next != null) {
            newHead.next = copyRandomList(head.next);
        }
        if (head.random != null) {
            newHead.random = map.get(head.random);
        }
        return newHead;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        n1.next = n2;
        n1.random = n1;
        n2.random = n1;
        Solution solution = new Solution();
        Node r = solution.copyRandomList(n1);
        System.out.println(r);

    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
